MazePathDiagonal.java

packagesection19_DynamicProgramming;

importjava.util.Arrays;

publicclassMazePathDiagonal {

publicstaticvoidmain(String[] args) {
intn = 500;
intcr = 0, cc = 0, er = n, ec = n;

// System.out.println(mazePathDiagonalRecursive(cr, cc, er, ec));
System.out.println(mazePathDiagonalTopDownDP(cr, cc, er, ec, newint[n + 1][n + 1]));
System.out.println(mazePathDiagBottomUpDP(er, ec));
System.out.println(mazePathDiagBottomUpSpaceEfficient(er, ec));
 }

// O(3^(er + ec)) Time | recursion extra space
publicstaticintmazePathDiagonalRecursive(intcr, intcc, inter, intec) {

if (cr > er || cc > ec) {
return0;
 }

if (cr == er && cc == ec) {
return1;
 }

inthorizontalCount = mazePathDiagonalRecursive(cr, cc + 1, er, ec);
intverticalCount = mazePathDiagonalRecursive(cr + 1, cc, er, ec);
intdiagonalCount = mazePathDiagonalRecursive(cr + 1, cc + 1, er, ec);

inttotalPaths = horizontalCount + verticalCount + diagonalCount;

returntotalPaths;
 }

// O(er*ec) Time | O(er*ec) Space + recursion extra space
publicstaticintmazePathDiagonalTopDownDP(intcr, intcc, inter, intec, int[][] storage) {

if (cr > er || cc > ec) {
return0;
 }
if (cr == er && cc == ec) {
return1;
 }
if (storage[cr][cc] != 0) {
returnstorage[cr][cc];
 }

inthorizontalCount = mazePathDiagonalTopDownDP(cr, cc + 1, er, ec, storage);
intverticalCount = mazePathDiagonalTopDownDP(cr + 1, cc, er, ec, storage);
intdiagonalCount = mazePathDiagonalTopDownDP(cr + 1, cc + 1, er, ec, storage);

inttotalPaths = horizontalCount + verticalCount + diagonalCount;

storage[cr][cc] = totalPaths;

returntotalPaths;
 }

// O(er*ec) Time | O(er*ec) Space
publicstaticintmazePathDiagBottomUpDP(inter, intec) {

int[][] storage = newint[er + 2][ec + 2];

for (introw = er; row >= 0; row--) {

for (intcol = ec; col >= 0; col--) {

if (row == er && col == ec) {
storage[row][col] = 1;
 } else {
storage[row][col] = storage[row][col + 1] + storage[row + 1][col] + storage[row + 1][col + 1];
 }
 }
 }

returnstorage[0][0];
 }

// O(er*ec) Time | O(ec) Space
publicstaticintmazePathDiagBottomUpSpaceEfficient(inter, intec) {
int[] storage = newint[ec + 1];

Arrays.fill(storage, 1);

for (intslide = er - 1; slide >= 0; slide--) {

intdiagonalvalue = 1;

for (intcol = ec; col >= 0; col--) {

if (col == ec) {
storage[col] = 1;
 } else {
intsum = storage[col] + storage[col + 1] + diagonalvalue;
diagonalvalue = storage[col];
storage[col] = sum;
 }
 }
 }

returnstorage[0];
 }
}